// ------------------------------------------------------------------------------------------------
// ---- Livro Algoritmos (de Cormen, Leiserson, Rivest, Stein) ------------------------------------
// ---- Problema da Subsequencia Comum Mais Longa (Capítulo 15.4) ---------------------------------
// ------------------------------------------------------------------------------------------------
#include <iostream>
using namespace std;


unsigned int LCS(string x, string y, char**& R);

void imprime_LCS(int i, int j, string x, char** R, string lcs);
void imprime_matriz(string x, string y, char** R);

// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
    string x = "ABCBDAB";
    string y = "BDCABA";
    cout << "Entrada X = " << x << "\n";
    cout << "Entrada Y = " << y << "\n\n";

    char** R = NULL;
    cout << "Tamanho da LCS = " << LCS(x,y,R);
    cout << "\n\n";

    string lcs;
    cout << "Todas as LCS's possiveis:\n";
    imprime_LCS(x.size(),y.size(),x,R,lcs);
    cout << "\n\n\n";

    imprime_matriz(x,y,R);
    if (R != NULL) {
        for (int i=0; i<=x.size(); i++) delete[] R[i];
        delete[] R;
    }
    cout << "\n";
    cout << "Simbolo \\ (diagonal)\n";
    cout << "Simbolo | (para cima)\n";
    cout << "Simbolo - (para esquerda)\n";
    cout << "Simbolo + (para ambos: cima ou esquerda)\n\n";
    return 0;
}


// -------------------------------------------------------------
// ---- ALGORITMO LCS (longest common subsequence) -------------
// -------------------------------------------------------------
unsigned int LCS(string x, string y, char**& R) {
    int i, j;
    int m = x.size();
    int n = y.size();
    int** c = new int*[m+1]; for (i=0; i<=m; i++) c[i]=new int[n+1];
    if(R==NULL){R=new char*[m+1];for(i=0;i<=m;i++)R[i]=new char[n+1];}

    for (i=0; i<=m; i++) c[i][0] = 0;
    for (j=0; j<=n; j++) c[0][j] = 0;

    for (i=1; i<=m; i++) {
        for (j=1; j<=n; j++) {
            if (x[i-1]==y[j-1]) {
                c[i][j] = c[i-1][j-1] + 1;
                R[i][j] = '\\';
            } else if (c[i-1][j]==c[i][j-1]) {
                c[i][j] = c[i-1][j];
                R[i][j] = '+';
            } else if (c[i-1][j]<c[i][j-1]) {
                c[i][j] = c[i][j-1];
                R[i][j] = '-';
            } else {
                c[i][j] = c[i-1][j];
                R[i][j] = '|';
            }
        }
    }
    int r = c[m][n];
    for (i=0; i<=m; i++) delete[] c[i];
    delete[] c;
    return r;
}

void imprime_LCS(int i, int j, string x, char** R, string lcs) {
    if ((i==0)||(j==0)) {
        cout << lcs << "\n";
        return;
    }

    if (R[i][j]=='\\') {
        lcs = string(1,x[i-1]) + lcs;
        imprime_LCS(i-1,j-1, x, R, lcs);
    } else if (R[i][j]=='+') {
        imprime_LCS(i-1,j, x, R, lcs);
        imprime_LCS(i,j-1, x, R, lcs);
    } else if (R[i][j]=='-') {
        imprime_LCS(i,j-1, x, R, lcs);
    } else {
        imprime_LCS(i-1,j, x, R, lcs);
    }
}

void imprime_matriz(string x, string y, char** R) {
    int m = x.size();
    int n = y.size();
    cout << "  " << y << "\n ";
    for (int j=0; j<=n; j++) cout << " ";
    cout << "\n";
    for (int i=1; i<=m; i++) {
        cout << x[i-1] << " ";
        for (int j=1; j<=n; j++) cout << R[i][j];
        cout << "\n";
    }
}